#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//char* intToRoman(int num)
//{
//    int i = 0;
//    int n = num;
//    char* arr = (char*)malloc(sizeof(char) * 16);
//    memset(arr, 0, 16);
//    int z = 0;
//    while (n)
//    {
//        n /= 10;
//        i++;
//    }
//    int k = 0;
//    for (k = 0; k < i; k++)
//    {
//        int j = ((int)(num / pow(10, i - k - 1))) % 10;
//        if (i - k == 4)
//        {
//            while (j--)
//            {
//                arr[z] = 'M';
//                z++;
//            }
//        }
//        else if (i - k == 3)
//        {
//            if (j >= 5 && j < 9)
//            {
//                arr[z] = 'Z';
//                z++;
//                j -= 5;
//                while (j--)
//                {
//                    arr[z] = 'C';
//                    z++;
//                }
//            }
//            else if (j == 9)
//            {
//                arr[z] = 'C';
//                z++;
//                arr[z] = 'M';
//                z++;
//            }
//            else if (j == 4)
//            {
//                arr[z] = 'C';
//                z++;
//                arr[z] = 'D';
//                z++;
//            }
//            else
//            {
//                while (j--)
//                {
//                    arr[z] = 'C';
//                    z++;
//                }
//            }
//        }
//        else if (i - k == 2)
//        {
//            if (j >= 5 && j < 9)
//            {
//                arr[z] = 'L';
//                z++;
//                j -= 5;
//                while (j--)
//                {
//                    arr[z] = 'X';
//                    z++;
//                }
//            }
//            else if (j == 9)
//            {
//                arr[z] = 'X';
//                z++;
//                arr[z] = 'C';
//                z++;
//            }
//            else if (j == 4)
//            {
//                arr[z] = 'X';
//                z++;
//                arr[z] = 'L';
//                z++;
//            }
//            else
//            {
//                while (j--)
//                {
//                    arr[z] = 'X';
//                    z++;
//                }
//            }
//        }
//        else if (i - k == 1)
//        {
//            if (j >= 5 && j < 9)
//            {
//                arr[z] = 'v';
//                z++;
//                j -= 5;
//                while (j--)
//                {
//                    arr[z] = 'I';
//                    z++;
//                }
//            }
//            else if (j == 9)
//            {
//                arr[z] = 'X';
//                z++;
//                arr[z] = 'I';
//                z++;
//            }
//            else if (j == 4)
//            {
//                arr[z] = 'I';
//                z++;
//                arr[z] = 'V';
//                z++;
//            }
//            else
//            {
//                while (j--)
//                {
//                    arr[z] = 'I';
//                    z++;
//                }
//            }
//        }
//    }
//    return arr;
//}

//char* intToRoman(int num) {
//    int digital[] = { 1,4,5,9,10,40,50,90,100,400,500,900,1000 };
//    char* alphabet[] = { "I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M" };
//
//    char* ret = (char*)malloc(sizeof(char) * 16);
//    memset(ret, 0, sizeof(ret));
//    for (int i = 12; i >= 0; i--)
//    {
//        while (num >= digital[i])
//        {
//            num -= digital[i];
//            strcat(ret, alphabet[i]);
//        }
//    }
//    return ret;
//}

//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        ListNode* p = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* pp = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* ph = pHead;
//        ListNode* p1 = p;
//        ListNode* p2 = pp;
//        p->next = NULL;
//        pp->next = NULL;
//        while (ph)
//        {
//            if (ph->val >= x)
//            {
//                pp->next = (ListNode*)malloc(sizeof(ListNode));
//                pp->next = ph;
//                ph = ph->next;
//                pp = pp->next;
//                pp->next = NULL;
//            }
//            else
//            {
//                p->next = (ListNode*)malloc(sizeof(ListNode));
//                p->next = ph;
//                ph = ph->next;
//                p = p->next;
//                p->next = NULL;
//            }
//        }
//        p->next = p2->next;
//        free(p2);
//        p2 = NULL;
//        ListNode* p3 = p1->next;
//        free(p1);
//        p1 = NULL;
//        return p3;
//    }
//};

//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    struct ListNode* ha = headA;
//    struct ListNode* hb = headB;
//    struct ListNode* hc = headB;
//    while (ha)
//    {
//        hb = hc;
//        while (hb)
//        {
//            if (ha == hb)
//            {
//                return hb;
//            }
//            hb = hb->next;
//        }
//        ha = ha->next;
//    }
//    return NULL;
//}
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    struct ListNode* ha = headA;
//    struct ListNode* hb = headB;
//    struct ListNode* hc = headB;
//    int x = 0;
//    int y = 0;
//    while (ha->next)
//    {
//        ha = ha->next;
//        x++;
//    }
//    while (hb->next)
//    {
//        hb = hb->next;
//        y++;
//    }
//    if (ha == hb)
//    {
//        ha = headA;
//        hb = headB;
//        int z = abs(x - y);
//        if (x > y)
//        {
//            while (z--)
//            {
//                ha = ha->next;
//            }
//        }
//        else
//        {
//            while (z--)
//            {
//                hb = hb->next;
//            }
//        }
//        while (ha != hb)
//        {
//            ha = ha->next;
//            hb = hb->next;
//        }
//        return ha;
//    }
//    return NULL;
//}
